from tools_algorithm import *


class Solution:
    def numberOfPairs(self, nums1: List[int], nums2: List[int], k: int) -> int:
        nums = [num // k for num in nums1 if num % k == 0]
        cnt = Counter(nums2)
        c = Counter(nums)
        ans = 0
        for num, s in c.items():
            i = 1
            while i * i < num:
                if num % i == 0:
                    ans += (cnt[i] + cnt[num // i]) * s
                i += 1
            if i * i == num:
                ans += cnt[i] * s
        return ans
